/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86187
 * Date: 2022-05-29
 * Time: 13:52
 */

public class TestList2 {
    /**
     * 给定单链表的头节点head，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
     * 第一个节点的索引被认为是 奇数 ， 第二个节点的索引为偶数 ，以此类推。
     * 请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
     * 你必须在O(1)的额外空间复杂度和O(n)的时间复杂度下解决这个问题。
     * @param head 头节点
     * @return head 头节点
     */
    public static Node oddEvenList(Node head) {
        if(head == null || head.next == null)
            return head;
        Node pos = head;
        Node ret = head.next;
        //ListNode pTail = pos;
        Node rHead = ret;
        while(pos.next != null && ret.next != null){
            //pTail = pos;
            pos.next = ret.next;
            pos = ret.next;
            ret.next = pos.next;
            ret = pos.next;
        }
        pos.next = rHead;
        return head;
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode();

        listNode.addLast(1);
        listNode.addLast(2);
        listNode.addLast(3);
        listNode.addLast(4);
        listNode.addLast(5);
        listNode.addLast(6);
        listNode.addLast(7);
        listNode.addLast(8);

        listNode.display(oddEvenList(listNode.head));
    }
}
